There are many aspects of control and management of information transmitted across a computer or telecommunications network, over and above the comparatively simple concept of traffic routing. These involve topics more concerned with the relationship between the network provider and the customer, such as cost, quality or level of service, priority and so on.
It is widely expected that the Internet will be reinvented as a converged packet-based platform for new services, delivering all forms of digital material into all types of application domain. This “Intelligent Internet” will need to differentiate between the needs of different traffic streams and allocate resources appropriately to meet those needs. In addition to considerable administrative support across the network, three principal Traffic Management mechanisms are required on the data fast path through the network routers. These are traffic classification, conditioning and handling.
Routers already determine where to send packets. Classification must additionally identify how packets should be treated as they are forwarded, the so-called Class of Service (CoS). A Conditioner then checks that each traffic stream complies with the terms of its Service Level Agreement (SLA). The SLA is a contract that specifies limits on the rates at which a customer is permitted to send traffic in different service classes. Finally, the Handler ensures that service guarantees are met by the provider. Typically, this is achieved through implementing a queue per available CoS. Each queue receives a prescribed quota of link bandwidth and packet buffer space.
As Traffic Management is something of a moving target, with new standards and improved algorithms constantly emerging, a programmable solution is considered to be a high priority. One problem facing engineers is how to design a programmable architecture with a useful processing cycle budget per packet at 40 Gbits/s line rates.
This may be illustrated by reference to FIG. 1, which shows a very simplified schematic diagram of part of the traffic handling portion of a network. The illustrated mechanism includes, in sequence, a traffic classifier A, traffic conditioner B, traffic handling system C and switch fabric S. Block C need not be located physically as in FIG. 1 but may be positioned before or after the switch fabric S. It is expected that data packets will be of varying size, ranging between 40 bytes, 1.5 kbytes, 9 kbytes and up to 16 kbytes.
The traffic classifier Block A has no facility for allocating bandwidth, charging and so on. Its main function is the identification of the class of service that a packet should receive. This typically involves a lookup operation, whereby a number of fields from the packet headers that can uniquely identify the packet with a microflow or flow aggregate are matched according to rules in a lookup table.
The traffic conditioner Block B performs a supervisory role in that it may decide that a customer is using too much bandwidth (say) and may mark that customer's packets with a corresponding marking. This is called “colouring” and the allocated markings may be, for example, “red”, “yellow” or “green”. Billing statistics may also be performed here and it may take account of the colouring applied to that packet or groups of packets.
The traffic conditioner enforces policy, which is specified in Traffic Conditioning Agreements (TCAs) between a network service provider and its customer. The TCA, which often forms part of the broader SLA, specifies agreed limits to traffic profiles entering (or leaving) the service provider network. Generally speaking, conditioners are therefore located in the boundary nodes of independently administered domains. Policy enforcement requires mechanisms which meter traffic streams to ensure that they comply with the terms of the TCA. “Out-of-profile” streams, ie those stepping outside the bounds of the TCA, may have excess traffic dropped—a measure referred to as policing. Alternatively, marking the packets as indicated above may be regarded as more acceptable. Marked packets may subsequently be discriminated against in the event of downstream traffic congestion.
The traffic handling system Block C decides when and how to put packets into an output buffer and to pull them out for onward transmission via the output port O/P of the illustrated section. Where the line rate is 40 Gbps, packet transmission rate is of the order of 100,000,000 packets per second and the rate at which packets are queued in the buffer ranges between 100s to 1,000s of Megabytes per second. It is the traffic handler which queues traffic and then applies scheduling and shaping mechanisms to forward it according to the required class of service. Scheduling disciplines ensure that traffic streams are protected from one another, that the link is shared fairly between streams, that performance bounds on guaranteed service traffic are met, and that congestion in the network is controlled.
At each stage, statistics may be gathered for administrative purposes The scope of traffic management also encompasses some other important administrative elements, such as policy management, system configuration, statistics processing, reporting, accounting and billing.
The functions performed by blocks A, B, and C are ideally carried out at line rate, for example at 40 Gbps. In the situation where C precedes S, it may not be possible to draw packets out of C into the switch fabric S at the line rate. Huge amounts of memory are therefore necessary to queue packets so as to come as close to the ideal as possible. As an aid to this process, C keeps records of packets rather than the packets themselves. These records are preferably of fixed size and contain information about the packets, which, of course, are themselves of variable size.
Where the system attempts to put packets into the line at a rate that is greater than the line rate (a condition known as “overspeed”) block C has to decide which packets are kept and which are held back or discarded. Block B monitors usage and attempts to provide individual customers with their agreed bandwidth but on an averaging basis. It will tolerate transient increases over the agreed bandwidth so long as the average is not exceeded over a given time period. In contrast, block C monitors the actual usage.
In traffic handling, packets may be placed in one of a number of queues. With more than one queue present, a scheduling function must determine the order in which packets are served from the queues. Control of this function is what is meant in this specification by “Order List Management”. The scheduled order is determined principally by the relative priorities that the scheduler places on the queues—not on the order in which packets arrived at the queues. The scheduling function is thus fairly serial in character.
For example, consider the two popular scheduling methods:
Fair Queue scheduling—every packet in the queue is given a finish number, which indicates the relative point in time that the packet is entitled to be outputted. The function that serves packets from the queue must identify the queue whose next packet has the smallest finish number. Ideally only after the packet has been served and the next packet in the same queue has been revealed can the dequeueing function make its next decision.
Round Robin scheduling—Queues are inspected in turn in a predetermined sequence. On each visit a prescribed quota of data may be served.
The fundamental problem is how to perform such scheduling algorithms at high speeds. A serialised process can only scale with clock/cycle frequency, or by increasing the depth of the processing pipe which makes the scheduling decision. This approach may only be able to provide a couple of system clock cycles per packet.
On top of this, the scheduling and queue management task is further confounded by a requirement for a large number of potentially very deep queues. Hardware, which executes the scheduling function in a serial manner, is then likely to be highly customised and therefore inflexible if it is to meet the required performance.